The background of the invention is described with reference to prior art publications referenced in Appendix A attached hereto.
The problem of fitting lines to a given set of data points is a well-known scientific and engineering task. In computer vision, for example, a digitized image may contain a number of discrete, `1` pixels lying on a `0` background, and the goal is the detection and parameter extraction of a number of straight lines that fit groups of collinear `1` pixels. A number of standard methods exist for such problems. Ordinary least squares methods, for example, seek to minimize the sum of squared vertical (or horizontal) distances of all points to the desired line. However, the resulting solutions are coordinate-system dependent; moreover in ordinary least squares, all measurement error is attributed to only one coordinate of the data points. To avoid these problems, the total least squares method (TLS) [1, 2] uses a criterion in which the sum of squared normal distances of all data points to the line is minimized. However, there are two major limitations that are inherited in all least squares approaches. One is the sensitivity of these methods to outliers. In other words, although the least squares methods can efficiently handle measurement errors that appear as small deviations in the point set, they cannot tolerate outliers; the existence of even a relatively small number of outliers tends to produce large residuals, leading to inadequate and unacceptable line fitting. The second main limitation of least squares methods lies in their inability to handle cases where there is more than one underlying line, especially crossing lines, in an image. The least squares method will result in an obviously wrong answer in these cases; see FIG. 1 for a simple example.
Another now classical method of finding line parameters to fit a given data point set, which is capable of handling multi-line problems, is the Hough transform [3, 4, 5], which is a special case of the Radon transform [6]. In this approach, first a special transformation is applied to all the points and then a two dimensional search is accomplished to find the maxima in the transform plane. The line parameters are .rho., the normal distance of the desired line from the origin, and .theta., the angle that the normal to the line makes with positive x-axis; .rho. and .theta. are also the coordinates in the Hough transform output plane. Each data point (x,y) is mapped under the Hough transform to the curve EQU .rho.=x cos .theta.+y sin .theta.
in the .rho.-.theta. plane. This equation also represents the line in the x-y plane that has a distance .rho. to the origin and the normal to it makes an angle .theta. with the x axis. Therefore, all the points in the x-y plane located on the line .rho..sub.0 =x cos .theta..sub.0 +y sin .theta..sub.0 are mapped to curves in the .rho.-.theta. plane that all pass through the point (.rho..sub.0,.theta..sub.0).
To fit a straight line to a set of data points, both .rho. and .theta. axes have to be quantized and hence a two-dimensional accumulator array be constructed in the .rho.-.theta. plane. The Hough transform equation is applied to each point in the data set and the contents of all the cells in the transform plane that the corresponding curve passes through are increased by one. This is done until all the data points are transformed and then, an exhaustive search will be needed to locate a number of maxima points in the .rho.-.theta. plane.
The Hough transform method is capable of handling a fairly high amount of noise contamination; however, it has certain drawbacks that may drastically limit its use. One problem, mentioned earlier, is the quantization of the .rho. and .theta. axes: to obtain an acceptable resolution, these coordinates need to be quantized finely, but reducing the quantization steps will broaden the peaks in the transform plane; in other words, since the actual measurement points for a line are not exactly collinear, the corresponding curves in the .rho.-.theta. plane do not pass through the same point. Certain procedures have been investigated to compensate for this difficulty in the quantization step of the Hough transform [7, 8, 9]. Secondly the burden of the two dimensional exhaustive search in the .rho.-.theta. plane for finding the maxima points is a serious drawback of the Hough transform, and this becomes more severe when the number of lines to be fitted to a given data set is unknown. In such cases, the existence of local maxima may cause the search to provide incorrect answers.
The present invention is directed to a new systematic multi-line fitting and straight edge detection procedure.